package datastructure.sort06;



import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 排序算法
 *
 * @Filename: SortTest
 * @Author: czh
 * @Data:2023/1/3 11:45
 * 排序算法
 * 冒泡排序
 * 选择排序
 * 插入排序
 * 希尔排序
 * 归并排序
 * 快速排序
 */
public class SortTest {
    int[] arr = new int[]{5, 6, 9, 7, 2, 8};

    /**
     * 冒泡排序
     * 思路来源: 观察水中气泡构思而成的
     * 思路分析: 又称交换排序法，从第一个元素开始，比较相邻元素的大小，若大小顺序有误,
     * 则对调后进行下一个元素的比较
     */
    @Test
    public void bubbleSort() {
        for (int i = 0; i < arr.length - 1; i++) {
            // 改进版冒泡排序
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                flag = true;
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            // 如果发现已经排好序了就直接跳出循环
            if (flag == false) {
                break;
            }
        }
        printSort(arr);
    }

    /**
     * 选择排序
     * 思路分析: 在所有数据中，设定一个哨兵找出数组中的最大值/最小值,
     * 然后去将该这放到第一位，依次想后找第二位第三位
     */
    @Test
    public void selectSort() {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                // 从小到大排序
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        printSort(arr);
    }

    /**
     * 插入排序
     * 思路分析: 每一次将一个待排序的数据插入前面已经排序号的序列中，直到插完所欲元素位置
     * 外层循环除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行插入位置查找，并进行移动
     */
    @Test
    public void insertSort() {
        int j;
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (temp < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = temp;
        }
        printSort(arr);
    }

    /**
     * 希尔排序(TODO)
     * 思路分析: 减少插入排序中数据的搬移的次数，将数据区分成特定间隔的几块小区块，以插入排序排完区块内的数据后在渐渐减少间隔的距离
     */
    @Test
    public void hashSort() {
        int jmp = arr.length / 2;  // jmp间隔位
        while (jmp != 0) {
            for (int i = jmp; i < arr.length; i++) {  //i表示扫描次数
                int temp = arr[i];
                int j = i - jmp;  //j来定位比较的元素
                while (j >= 0 && temp < arr[j]) {
                    arr[j + jmp] = arr[j];
                    j = j - jmp;
                }
                arr[jmp + j] = temp;
            }
            jmp = jmp / 2;
        }
        printSort(arr);
    }

    /**
     * 归并排序法
     * 思路分析: 先将待排序的序列一次次分成子序列，知道子序列长度为1,
     * 再将子序列合并成一个完全有序的序列
     */
    @Test
    public void mergeSort() {
        int[] result = new int[arr.length];
        process(arr, 0, arr.length - 1, result);
        System.out.println(Arrays.toString(result));
    }

    // 分治操作
    public static void process(int[] arr, int left, int right, int[] result) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 左边递归分解
            process(arr, left, mid, result);
            // 右边递归分解
            process(arr, mid + 1, right, result);
            // 合并
            merge(arr, left, mid, right, result);
        }
    }

    // 合并操作
    public static void merge(int[] arr, int left, int mid, int right, int[] result) {
        //左边有序序列的初始索引
        int i = left;
        //右边有序序列的初始索引
        int j = mid + 1;
        int t = 0; // 指向临时数组的当前索引
        //将两边数组的元素进行比较，依次填进临时数组
        //直到将一边填完
        while (i <= mid && j <= right) {
            //选择较小的添加进去
            if (arr[i] <= arr[j]) {
                result[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                result[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //把有剩余数据的数组全部填充到数组
        //肉眼可以判别哪个有数据，但是计算机需要用循环条件判别
        //所以有两个while循环
        while (i <= mid) {
            result[t] = arr[i];
            t += 1;
            i += 1;
        }

        while (j <= right) {
            result[t] = arr[j];
            t += 1;
            j += 1;
        }

        //将temp数组的元素拷贝到arr
        t = 0;
        int Left = left;
        while (Left <= right) {
            arr[Left] = result[t];
            t += 1;
            Left += 1;
        }
    }

    /**
     * 快速排序
     * 1.先选择基数(一般选择第一个)并选择两个指针（开始i和结束j）,先从结束j的往前走直到找到一个值大于基数，在从开始i往后走
     * 直到找到小于基数的值停下，并交换ij的值，如果ij相遇则将基数的的值和相遇值进行交换
     * 2.
     */
//    @Test
    public void quickSort(int[] arr, int low, int hight) {
        int i, j, temp, t;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        // 基准数
        temp = arr[i];
        while (i < j) {
            // 先看右边，依次往左递减
            // 先看右边的原因: 如果从左边先开始的话，有可能发生当i和j相遇的值是大于基准值，这就违背了快速排序的条件
            while (temp <= arr[j] && i < j) {
                j--;
            }
            // 再看左边、依次往右递减
            while (temp >= arr[i] && i < j) {
                i++;
            }
            // 找到左边和右边的值进行交换
            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        // 将基准数和i，j位置相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        // 递归调用左边数组
        quickSort(arr, low, j - 1);
        // 递归调用左边数组
        quickSort(arr, j + 1, hight);
    }

    public static void printSort(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            System.out.print(arr[k] + " ");
        }
    }

//    public static void main(String[] args) {
//        int[] arrs = new int[]{5, 6, 9, 7, 2, 8};
////        quickSort(arrs, 0, arrs.length - 1);
//        printSort(arrs);
//    }


}